//https://leetcode-cn.com/problems/balanced-binary-tree/
//平衡二叉树
//给定一个二叉树，判断它是否是 平衡二叉树
//平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。


//方法一
int judge(struct TreeNode* root)
{
    if(root == NULL)
    return 0;

    int leftHeight = judge(root->left);
    int rightHeight = judge(root->right);

    if(leftHeight == -1 || rightHeight == -1)
    return -1;
    else
    {
        if(leftHeight >= rightHeight && leftHeight - rightHeight <= 1)
        return leftHeight + 1;
        else if(rightHeight > leftHeight && rightHeight - leftHeight <= 1)
        return rightHeight + 1;
        else
        return -1;
    }
}

bool isBalanced1(struct TreeNode* root) {
    if(judge(root) == -1)
    return false;
    else
    return true;
}





//方法二
int maxDepth(struct TreeNode* root){
    return root ? 1 + fmax(maxDepth(root->left) , maxDepth(root->right)) : 0;      
}

bool isBalanced2(struct TreeNode* root){
    if(root == NULL)
        return true;
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return abs(left - right) < 2
        && isBalanced2(root->left)
        && isBalanced2(root->right);
}